#ifndef DEQUE_H_INCLUDED
#define DEQUE_H_INCLUDED

#include "Atomic.h"
#include "Vector.h"
#include "IteratorForward.h"

namespace CEngine {

template<class Element>
class Deque {
        struct DequeIterator;

    public:

        ///Creates an empty Deque. Does not allocate memory.
        Deque(void);

        ///Creates a Deque numberOfElements long, elements use a blank constructor.
        Deque(const U64 numberOfElements);

        ///Creates a Deque numberOfElements long, elements are all set to defaultValue.
        Deque(const U64 numberOfElements, const Element& defaultValue);

        ///Creates a Deque made of the elements between first and last (including first, but not last).
        Deque(const Iterator<Element>& first, const Iterator<Element>& last);

        ///Creates a copy of Deque.
        Deque(const Deque& Deque);

        ///Copies the contents of Deque (destroys all previous elements).
        ///Space used will not decrease.
        Deque&
        operator= (const Deque& Deque);

        ///Destructor.
        ~Deque(void);

        ///Iterator function. Returns an iterator to the first element in the Deque.
        DequeIterator
        begin(void) const;

        ///Iterator function. Returns an iterator to the last element in the Deque.
        DequeIterator
        rBegin(void) const;

        ///Iterator function. Returns an iterator to the element after the end of the Deque.
        ///Do not dereference.
        DequeIterator
        end(void) const;

        ///Iterator function. Returns an iterator to the element before the start of the Deque.
        ///Do not dereference.
        DequeIterator
        rEnd(void) const;

        ///Access function. Returns the element at the front of the deque.
        Element&
        front(void);

        ///Access function. Returns the element at the end of the deque.
        Element&
        back(void);

        ///Adds element to the beginning of the deque.
        void
        pushFront(const Element& element);

        ///Deletes the first element in the deque.
        void
        popFront(void);

        ///Adds element to the end of the deque.
        void
        pushBack(const Element& element);

        ///Deletes the last element in the Deque.
        void
        popBack(void);

        ///Removes every element from the deque. Memory is not freed.
        void
        clear(void);

        ///Returns if there are any elements in the deque.
        bool
        isEmpty(void) const;

        ///Returns the size of the deque (in elements).
        U64
        getSize(void) const;

    private:

        Vector<Element*> array;
        U64 size;
        U64 start;

        U64 startArray;
        U64 startIndice;
        Element* startPointer;

        U64 endArray;
        U64 endIndice;
        Element* endPointer;

        Element& getElement(const U64 position);

        template<class E, class K> friend class Iterator;

        ///Iterator initializer used by the generic Iterator class
        struct DequeIterator {
            Deque<Element>* basePointer;
            Element** currentArray;
            Element* startPointer;
            Element* currentPointer;
            Element* endPointer;
            U64 position;
        };
};

}

#include "DequeCore.h"

#endif // DEQUE_H_INCLUDED
